import numpy as np
import matplotlib.pyplot as plt
import math
import random

#load data from csv file
data1= np.loadtxt(open('dataset_circles.csv'),delimiter=",",skiprows=0)
x1=data1[:,0]
x2=data1[:,1]
plt.scatter(x1,x2,c=data1[:,2])
plt.title("Initial Data")
plt.show()
data=data1[:,:2]#用作归类的数据我们值保留他的坐标值

def distance_calc(a1,a2):
    return np.sum(np.square(a1-a2))
def rand_cluster_center(target,k):
    """打乱下标，选取k个初始点"""
    x=np.shape(target)[0]
    data_index=list(range(0,x))
    random.shuffle(data_index)
    centers_index=data_index[:k]
    return target[centers_index,:]#numpy数组的花式索引,只保留坐标

def kmeans(data,k):
    m= np.shape(data)[0]
    # 在迭代过程中个每个数据一个类标签，故需要写成2列的数组
    cluster_process=np.zeros((m,2))
    #centers是选取的重心点组成的数组，应该是k行2列的形式
    centers=rand_cluster_center(data,k)
    n=np.shape(centers)[0]
    print("The initial centers ","\n",centers)

    iteration=0 #迭代计数
    while True:
        #我们让循环初始值为false如果不改变则break
        cluster_change=False
        # 更新每个点所属的类别
        for i in range(m):#对每个点进行判断
            #定义初始的最小距离以及索引值
            min_dist=np.inf
            min_index=-1
            for j in range(n):
                #遍历第i个样本点和j个重心点距离，取最小，更新最小距离和类别
                distance=distance_calc(centers[j,:],data[i,:])
                if distance<min_dist:
                    min_dist=distance #update minimum distance
                    min_index=j #update cluster
            # j的循环里先记下了最小距离及索引，再和原来的对比，看是否需要更新
            if cluster_process[i][0]!=min_index:
                cluster_change=True
            #存入cluster_process的是min_dist的平方，方便后续计算
            cluster_process[i,:]=min_index,min_dist
        iteration+=1

        #更新每个类别的重心
        for p in range(k):
            #从cluster_process中提取第k类的下标，然后用data中样本求重心横纵坐标
            samples=data[cluster_process[:,0]==p,:]
            x1=np.mean(samples[:,0])
            x2=np.mean(samples[:,1])
            centers[p]=[x1,x2]

        #在所有工作结束之后，判断是否还要进行下一次迭代
        if iteration>20000 or cluster_change==False:
            # 在迭代完成之后输出数据
            distance_all = sum(cluster_process[:, 1])
            print("第%d次迭代，所有数据点到重心距离之和：" % iteration + str(distance_all))
            break
    return centers,cluster_process

# Result Display
def data_display(data, k, centers, cluster_process):
    import matplotlib.pyplot as plt
    # 绘制样本点的分类结果
    marksamples = ['or', 'ob', 'og', 'ok', '^r', '^b', '<g']
    if k > len(marksamples):
        print("Please add enough marks to show the samples")
    num = np.shape(data)[0]
    for i in range(num):
        markindex = int(cluster_process[i, 0])  # 样本类别决定mark记号，索引值取整
        # 画出第i个点的横纵坐标，用markindex决定记号
        plt.plot(data[i, 0], data[i, 1], marksamples[markindex])

    # 绘制重心点结果
    #定义标志、颜色、图例序号
    markcenters = ['o', '*']
    c = ['yellow', 'green']
    labels=["0","1"]
    if k > len(markcenters):
        print("Please add enough marks to show the centers")
    for j in range(k):
        plt.plot(centers[j,0],centers[j,1],markcenters[j],\
                 label=labels[j],c=c[j],markersize=16)
    plt.xlabel("x axis")
    plt.ylabel("y axis")
    plt.title("Result of clustering")
    plt.show()

#main process
k=2
centers,cluster_process=kmeans(data,2)
data_display(data,k,centers,cluster_process)


